package class7;

import common.ListNode;
import common.TreeNode;
import common.TreeNodeUtils;


public class TestDemo {

    public static void main(String[] args) {
        TreeNode treeNode = getTreeNode();
    }


    // 判断链表是否有环
    private static boolean isLoopNode(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        ListNode s = head.next;
        ListNode f = head.next.next;
        while (s != f) {
            if (f.next == null || f.next.next == null) {
                return false;
            }
            s = s.next;
            f = f.next.next;
        }
        return true;
    }

    // 判断链表是否有环,进入环的第一个节点
    private static ListNode isLoopNode2(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode s = head.next;
        ListNode f = head.next.next;
        while (s != f) {
            if (f.next == null || f.next.next == null) {
                return null;
            }
            s = s.next;
            f = f.next.next;
        }
        f = head;
        while (f != s) {
            f = f.next;
            s = s.next;
        }
        return f;
    }

    // 判断链表是否有环,进入环的第一个节点
    private static ListNode isLoopNode3(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        int n = 0;
        ListNode c1 = head1;
        ListNode c2 = head2;
        // 先判断尾节点是否相同
        while (c1 != null) {
            c1 = c1.next;
            n++;
        }
        while (c2 != null) {
            c2 = c2.next;
            n--;
        }
        if (c1 != c2) {
            return null;
        }
        c1 = n > 0 ? head1 : head2;
        c2 = c1 == head1 ? head2 : head1;
        n = Math.abs(n);
        // 先让c1走 n步
        while (n > 0) {
            c1 = c1.next;
            n--;
        }
        while (c1 != c2) {
            c1 = c1.next;
            c2 = c2.next;
        }
        return c1;
    }


    private static TreeNode getTreeNode() {
        /**
         *       5
         *     /   \
         *    4     8
         *   11    13 4
         *  7  2       1
         */

        TreeNode root = TreeNodeUtils.createTreeNode(5, 4, 8);
        TreeNode[] thr = TreeNodeUtils.getTreeNodes(11, 13, 4);
        TreeNode[] foth = TreeNodeUtils.getTreeNodes(7, 2, 1);

        thr[0].left = foth[0];
        thr[0].right = foth[1];
        thr[2].right = foth[2];
        root.left.left = thr[0];
        root.right.left = thr[1];
        root.right.right = thr[2];
        return root;
    }
}
